Search for: All records

Boosting Employment of Resettled Refugees Whether a resettled refugee finds employment in the United States depends in no small part on which host community they are first welcomed to. Every week, resettlement agencies are assigned a group of refugees who they are required to place in communities around the country. In “Dynamic Placement in Refugee Resettlement,” Ahani, Gölz, Procaccia, Teytelboym, and Trapp develop an allocation system that recommends where to place an incoming refugee family with the aim of boosting the overall employment success. Should capacities in high-employment areas be used up as quickly as possible, or does it make sense to hold back for a perfect match? The simple algorithm, based on two-stage stochastic programming, achieves over 98% of the hindsight-optimal employment, compared with under 90% for the greedy-like approaches that were previously used in practice. Their algorithm is now part of the Annie™ MOORE optimization software used by a leading American refugee resettlement agency. 

Motivated by kidney exchange, we study the following mechanism-design problem: On a directed graph (of transplant compatibilities among patient--donor pairs), the mechanism must select a simple path (a chain of transplantations) starting at a distinguished vertex (an altruistic donor) such that the total length of this path is as large as possible (a maximum number of patients receive a kidney). However, the mechanism does not have direct access to the graph. Instead, the vertices are partitioned over multiple players (hospitals), and each player reports a subset of her vertices to the mechanism. In particular, a player may strategically omit vertices to increase how many of her vertices lie on the path returned by the mechanism. Our objective is to find mechanisms that limit incentives for such manipulation while producing long paths. Unfortunately, in worst-case instances, competing with the overall longest path is impossible while incentivizing (approximate) truthfulness, i.e., requiring that hiding nodes cannot increase a player's utility by more than a factor of 1 + o(1). We therefore adopt a semi-random model where o(n) random edges are added to worst-case instances. While it remains impossible for truthful mechanisms to compete with the overall longest path, we give a truthful mechanism that competes with a weaker but non-trivial benchmark: the length of any path whose subpaths within each player have a minimum average length. In fact, our mechanism satisfies even a stronger notion of truthfulness, which we call matching-time incentive compatibility. This notion of truthfulness requires that each player not only reports her nodes truthfully but also does not stop the returned path at any of her nodes in order to divert it to a continuation inside her own subgraph. 

Employment outcomes of resettled refugees depend strongly on where they are placed inside the host country. While the United States sets refugee capacities for communities on an annual basis, refugees arrive and must be placed over the course of the year. We introduce a dynamic allocation system based on two-stage stochastic programming to improve employment outcomes. Our algorithm is able to achieve over 98 percent of the hindsight-optimal employment compared to under 90 percent of current greedy-like approaches. This dramatic improvement persists even when we incorporate a vast array of practical features of the refugee resettlement process including indivisible families, batching, and uncertainty with respect to the number of future arrivals. Our algorithm is now part of the Annie™ MOORE optimization software used by a leading American refugee resettlement agency. The full version of this paper is available at https://arxiv.org/pdf/2105.14388.pdf.